package com.study.daily.algozuo.y2022.m01.day0108;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/1/8 上午 10:46
 * @version: 1.0
 */
public class Code01_RobotWalk {
    // 间距是从1到N;
    // start为初始位置
    // aim为目标位置
    // K，是需要走K步
    public static int ways1(int N, int start, int aim, int K) {
        return process1(start, K, N, aim);
    }

    // 间距为N， 需要走K步
    public static int process1(int cur, int rest, int N, int aim) {
        if (rest == 0) {
            return cur == aim ? 1 : 0;
        }
        if (cur == 1) {
            process1(2, rest - 1, N, aim);
        }
        if (cur == N) {
            process1(N - 1, rest - 1, N, aim);
        }
        return process1(cur - 1, rest - 1, N, aim) + process1(cur + 1, rest - 1, N, aim);
    }

    public static int ways2(int N, int start, int aim, int K) {
        int[][] dp = new int[N + 1][K + 1];
        for (int cur = 1; cur <= N; cur++) {
            dp[cur][0] = cur == aim ? 1 : 0;
        }
        for(int rest = 1; rest <= K; rest++){
            dp[1][rest] = dp[2][rest-1];
            for(int cur = 2; cur < N; cur++){
                dp[cur][rest] = dp[cur-1][rest-1] + dp[cur+1][rest-1];
            }
            dp[N][rest] = dp[N-1][rest-1];
        }
        return dp[start][K];
    }

    public static int ways3(int N, int start, int aim, int K){
        int[][] dp = new int[N+1][K+1];
        for (int i = 0; i < N+1; i++) {
            for (int j = 0; j < K+1; j++) {
                dp[i][j] = -1;
            }
        }
        return process3(N, start, aim, K, dp);
    }

    public static int process3(int N, int cur, int aim, int rest, int[][] dp){
        if(dp[cur][rest] != -1){
            return dp[cur][rest];
        }
        int ans = 0;
        if(rest == 0){
            ans = cur == aim ? 1 :0;
        } else if(cur == 0){
            ans = process3(N, 1, aim, rest - 1,dp);
        } else if(cur == N) {
            ans = process3(N, N - 1, aim, rest - 1, dp);
        } else {
            ans = process3(N, cur - 1, aim, rest-1,dp) + process3(N, cur + 1, aim, rest - 1,dp);
        }
        dp[cur][rest] = ans;
        return dp[cur][rest];
    }

    public static void main(String[] args) {
        int N = 5;
        int K = 4;
        int aim = 3;
        int start = 3;
        int ways1 = ways1(N, start, aim, K);
        int ways2 = ways2(N, start, aim, K);
        int ways3 = ways3(N, start, aim, K);
        System.out.println(ways1);
        System.out.println(ways2);
        System.out.println(ways3);
    }
}
